SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Pointclass</title>

</head>

Pointclass

</h1>

</header>

In the mathematical field of <a href="Descriptive_set_theory" title="Descriptive set theory">descriptive set theory</a>, a pointclass is a collection of <a href="Set_(mathematics)" title="Set (mathematics)">sets</a> of <a href="Point_(mathematics)" class="mw-redirect" title="Point (mathematics)">points</a>, where a point is ordinarily understood to be an element of some <a href="Perfect_set" title="Perfect set">perfect</a> <a href="Polish_space" title="Polish space">Polish space</a>. In practice, a pointclass is usually characterized by some sort of definability property; for example, the collection of all <a href="Open_set" title="Open set">open sets</a> in some fixed collection of Polish spaces is a pointclass. (An open set may be seen as in some sense definable because it cannot be a purely arbitrary collection of points; for any point in the set, all points sufficiently close to that point must also be in the set.)

Pointclasses find application in formulating many important principles and theorems from <a href="Set_theory" title="Set theory">set theory</a> and <a href="Real_analysis" title="Real analysis">real analysis</a>. Strong set-theoretic principles may be stated in terms of the <a href="Determinacy" title="Determinacy">determinacy</a> of various pointclasses, which in turn implies that sets in those pointclasses (or sometimes larger ones) have regularity properties such as <a href="Lebesgue_measure" title="Lebesgue measure">Lebesgue measurability</a> (and indeed <a href="Universally_measurable_set" title="Universally measurable set">universal measurability</a>), the <a href="Property_of_Baire" title="Property of Baire">property of Baire</a>, and the <a href="Perfect_set_property" title="Perfect set property">perfect set property</a>.

<div class="mw-heading mw-heading2"><h2 id="Basic_framework">Basic framework</h2></div>

In practice, descriptive set theorists often simplify matters by working in a fixed Polish space such as <a href="Baire_space_(set_theory)" title="Baire space (set theory)">Baire space</a> or sometimes <a href="Cantor_space" title="Cantor space">Cantor space</a>, each of which has the advantage of being <a href="Zero_dimensional" class="mw-redirect" title="Zero dimensional">zero dimensional</a>, and indeed <a href="Homeomorphic" class="mw-redirect" title="Homeomorphic">homeomorphic</a> to its finite or countable <a href="Product_topology" title="Product topology">powers</a>, so that considerations of dimensionality never arise. <a href="Yiannis_Moschovakis" class="mw-redirect" title="Yiannis Moschovakis">Yiannis Moschovakis</a> provides greater generality by fixing once and for all a collection of underlying Polish spaces, including the set of all naturals, the set of all reals, Baire space, and Cantor space, and otherwise allowing the reader to throw in any desired perfect Polish space. Then he defines a product space to be any finite <a href="Cartesian_product" title="Cartesian product">Cartesian product</a> of these underlying spaces. Then, for example, the pointclass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}</annotation>

</semantics>

</math><img src="./b9cd4e8164e11f1b362aa74c89d3c713d77525a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.985ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}" loading="lazy"> of all open sets means the collection of all open subsets of one of these product spaces. This approach prevents <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}</annotation>

</semantics>

</math><img src="./b9cd4e8164e11f1b362aa74c89d3c713d77525a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.985ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}" loading="lazy"> from being a <a href="Proper_class" class="mw-redirect" title="Proper class">proper class</a>, while avoiding excessive specificity as to the particular Polish spaces being considered (given that the focus is on the fact that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}</annotation>

</semantics>

</math><img src="./b9cd4e8164e11f1b362aa74c89d3c713d77525a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.985ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}" loading="lazy"> is the collection of open sets, not on the spaces themselves).

<div class="mw-heading mw-heading2"><h2 id="Boldface_pointclasses">Boldface pointclasses</h2></div>

The pointclasses in the <a href="Borel_hierarchy" title="Borel hierarchy">Borel hierarchy</a>, and in the more complex <a href="Projective_hierarchy" title="Projective hierarchy">projective hierarchy</a>, are represented by sub- and super-scripted Greek letters in <a href="Boldface" class="mw-redirect" title="Boldface">boldface</a> fonts; for example, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Pi }}_{1}^{0}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Pi }}_{1}^{0}}</annotation>

</semantics>

</math><img src="./895ab010733ba801f607f2c764c66b74b4733ee7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.146ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Pi }}_{1}^{0}}" loading="lazy"> is the pointclass of all <a href="Closed_set" title="Closed set">closed sets</a>, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Sigma }}_{2}^{0}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Sigma }}_{2}^{0}}</annotation>

</semantics>

</math><img src="./7c611a26a9ae8f91ad7d6b170fbae9e827726a01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.985ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Sigma }}_{2}^{0}}" loading="lazy"> is the pointclass of all <a href="F-sigma" class="mw-redirect" title="F-sigma">Fσ</a> sets, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Delta }}_{2}^{0}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Delta }}_{2}^{0}}</annotation>

</semantics>

</math><img src="./c63a8db1ac7d9d4ae01748d9cf2a38ae7567e604.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.28ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Delta }}_{2}^{0}}" loading="lazy"> is the collection of all sets that are simultaneously Fσ and <a href="G-delta_set" class="mw-redirect" title="G-delta set">Gδ</a>, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}}</annotation>

</semantics>

</math><img src="./042b5e70808bbd6ee37581811278d41b9712d03b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.985ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{1}}" loading="lazy"> is the pointclass of all <a href="Analytic_set" title="Analytic set">analytic sets</a>.

Sets in such pointclasses need be "definable" only up to a point. For example, every <a href="Singleton_set" class="mw-redirect" title="Singleton set">singleton set</a> in a Polish space is closed, and thus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Pi }}_{1}^{0}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Pi }}_{1}^{0}}</annotation>

</semantics>

</math><img src="./895ab010733ba801f607f2c764c66b74b4733ee7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.146ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Pi }}_{1}^{0}}" loading="lazy">. Therefore, it cannot be that every <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Pi }}_{1}^{0}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Pi }}_{1}^{0}}</annotation>

</semantics>

</math><img src="./895ab010733ba801f607f2c764c66b74b4733ee7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.146ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Pi }}_{1}^{0}}" loading="lazy"> set must be "more definable" than an arbitrary element of a Polish space (say, an arbitrary real number, or an arbitrary countable sequence of natural numbers). Boldface pointclasses, however, may (and in practice ordinarily do) require that sets in the class be definable relative to some real number, taken as an <a href="Oracle_machine" title="Oracle machine">oracle</a>. In that sense, membership in a boldface pointclass is a definability property, even though it is not absolute definability, but only definability with respect to a possibly undefinable real number.

Boldface pointclasses, or at least the ones ordinarily considered, are closed under <a href="Wadge_reducibility" class="mw-redirect" title="Wadge reducibility">Wadge reducibility</a>; that is, given a set in the pointclass, its <a href="Inverse_image" class="mw-redirect" title="Inverse image">inverse image</a> under a <a href="Continuous_function" title="Continuous function">continuous function</a> (from a product space to the space of which the given set is a subset) is also in the given pointclass. Thus a boldface pointclass is a downward-closed union of <a href="Wadge_degree" class="mw-redirect" title="Wadge degree">Wadge degrees</a>.

<div class="mw-heading mw-heading2"><h2 id="Lightface_pointclasses">Lightface pointclasses</h2></div>

The Borel and projective hierarchies have analogs in <a href="Effective_descriptive_set_theory" title="Effective descriptive set theory">effective descriptive set theory</a> in which the definability property is no longer relativized to an oracle, but is made absolute. For example, if one fixes some collection of basic <a href="Open_neighborhood" class="mw-redirect" title="Open neighborhood">open neighborhoods</a> (say, in Baire space, the collection of sets of the form {x∈ωω <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mid }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mid }</annotation>

</semantics>

</math><img src="./8f7b2136e276c4aec285a6c40b91180c16432b9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.647ex; height:2.843ex;" alt="{\displaystyle \mid }" loading="lazy"> s is an initial segment of x} for each fixed finite sequence s of natural numbers), then the open, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}</annotation>

</semantics>

</math><img src="./b9cd4e8164e11f1b362aa74c89d3c713d77525a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.985ex; height:3.176ex;" alt="{\displaystyle {\boldsymbol {\Sigma }}_{1}^{0}}" loading="lazy">, sets may be characterized as all (arbitrary) unions of basic open neighborhoods. The analogous <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma _{1}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{1}^{0}}</annotation>

</semantics>

</math><img src="./8130a55f302deb0b733de5a526f2d92c364e4dd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.732ex; height:3.176ex;" alt="{\displaystyle \Sigma _{1}^{0}}" loading="lazy"> sets, with a lightface <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy">, are no longer arbitrary unions of such neighborhoods, but <a href="Computable_set" title="Computable set">computable</a> unions of them. That is, a set is lightface <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma _{1}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{1}^{0}}</annotation>

</semantics>

</math><img src="./8130a55f302deb0b733de5a526f2d92c364e4dd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.732ex; height:3.176ex;" alt="{\displaystyle \Sigma _{1}^{0}}" loading="lazy">, also called effectively open, if there is a computable set S of finite sequences of naturals such that the given set is the union of the sets {x∈ωω <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mid }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mid }</annotation>

</semantics>

</math><img src="./8f7b2136e276c4aec285a6c40b91180c16432b9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:0.647ex; height:2.843ex;" alt="{\displaystyle \mid }" loading="lazy"> s is an initial segment of x} for s in S.

A set is lightface <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi _{1}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi _{1}^{0}}</annotation>

</semantics>

</math><img src="./b0b3c0e79d8a5db977a9838be477eb3e30348937.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.797ex; height:3.176ex;" alt="{\displaystyle \Pi _{1}^{0}}" loading="lazy"> if it is the complement of a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma _{1}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{1}^{0}}</annotation>

</semantics>

</math><img src="./8130a55f302deb0b733de5a526f2d92c364e4dd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.732ex; height:3.176ex;" alt="{\displaystyle \Sigma _{1}^{0}}" loading="lazy"> set. Thus each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma _{1}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{1}^{0}}</annotation>

</semantics>

</math><img src="./8130a55f302deb0b733de5a526f2d92c364e4dd6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.732ex; height:3.176ex;" alt="{\displaystyle \Sigma _{1}^{0}}" loading="lazy"> set has at least one index, which describes the computable function enumerating the basic open sets from which it is composed; in fact it will have infinitely many such indices. Similarly, an index for a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi _{1}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi _{1}^{0}}</annotation>

</semantics>

</math><img src="./b0b3c0e79d8a5db977a9838be477eb3e30348937.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.797ex; height:3.176ex;" alt="{\displaystyle \Pi _{1}^{0}}" loading="lazy"> set B describes the computable function enumerating the basic open sets in the complement of B.

A set A is lightface <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma _{2}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma _{2}^{0}}</annotation>

</semantics>

</math><img src="./09ae5829fb5735899799870a3156c903f0573f60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.732ex; height:3.176ex;" alt="{\displaystyle \Sigma _{2}^{0}}" loading="lazy"> if it is a union of a computable sequence of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi _{1}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi _{1}^{0}}</annotation>

</semantics>

</math><img src="./b0b3c0e79d8a5db977a9838be477eb3e30348937.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.797ex; height:3.176ex;" alt="{\displaystyle \Pi _{1}^{0}}" loading="lazy"> sets (that is, there is a computable enumeration of indices of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi _{1}^{0}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi _{1}^{0}}</annotation>

</semantics>

</math><img src="./b0b3c0e79d8a5db977a9838be477eb3e30348937.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.797ex; height:3.176ex;" alt="{\displaystyle \Pi _{1}^{0}}" loading="lazy"> sets such that A is the union of these sets). This relationship between lightface sets and their indices is used to extend the lightface Borel hierarchy into the transfinite, via <a href="Recursive_ordinal" class="mw-redirect" title="Recursive ordinal">recursive ordinals</a>. This produces the <a href="Hyperarithmetic_hierarchy" class="mw-redirect" title="Hyperarithmetic hierarchy">hyperarithmetic hierarchy</a>, which is the lightface analog of the Borel hierarchy. (The finite levels of the <a href="Hyperarithmetical_theory" title="Hyperarithmetical theory">hyperarithmetic hierarchy</a> are known as the <a href="Arithmetical_hierarchy" title="Arithmetical hierarchy">arithmetical hierarchy</a>.)

A similar treatment can be applied to the projective hierarchy. Its lightface analog is known as the <a href="Analytical_hierarchy" title="Analytical hierarchy">analytical hierarchy</a>.

<div class="mw-heading mw-heading2"><h2 id="Summary">Summary</h2></div>

Each class is at least as large as the classes above it.

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar-header{text-align:center;position:relative;white-space:nowrap}.mw-parser-output .navbar-header .navbar{position:absolute;right:0;top:0;margin:0 5px}

/* end https://en.wikipedia.org/ */

</style><div class="navbar-header"><a href="Pointclasses" class="mw-redirect" title="Pointclasses">Pointclasses</a><style data-mw-deduplicate="TemplateStyles:r1129693374">

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div>

</th></tr>

<tr>

/* start https://en.wikipedia.org/ */

.mw-parser-output .nobold{font-weight:normal}

/* end https://en.wikipedia.org/ */

</style><a href="Lightface_hierarchy" class="mw-redirect" title="Lightface hierarchy">Lightface</a>

</th>

<th colspan="2"><a href="Boldface_hierarchy" class="mw-redirect" title="Boldface hierarchy">Boldface</a>

</th></tr>

<tr>

<td colspan="2">Σ0 0 = Π0 0 = Δ0 0 (sometimes the same as Δ0 1)

</td>

<td colspan="2">Σ0 0 = Π0 0 = Δ0 0 (if defined)

</td></tr>

<tr>

<td colspan="2">Δ0 1 = <a href="Computable_set" title="Computable set">recursive</a>

</td>

<td colspan="2">Δ0 1 = <a href="Clopen_set" title="Clopen set">clopen</a>

</td></tr>

<tr>

<td>Σ0 1 = <a href="Computably_enumerable_set" title="Computably enumerable set">recursively enumerable</a>

</td>

<td>Π0 1 = co-recursively enumerable

</td>

</td>

<td>Π0 1 = F = <a href="Closed_set" title="Closed set">closed</a>

</td></tr>

<tr>

<td colspan="2">Δ0 2

</td>

<td colspan="2">Δ0 2

</td></tr>

<tr>

<td>Σ0 2

</td>

<td>Π0 2

</td>

</td>

</td></tr>

<tr>

<td colspan="2">Δ0 3

</td>

<td colspan="2">Δ0 3

</td></tr>

<tr>

<td>Σ0 3

</td>

<td>Π0 3

</td>

<td>Σ0 3 = Gδσ

</td>

<td>Π0 3 = Fσδ

</td></tr>

<tr>

<td colspan="2">⋮

</td>

<td colspan="2">⋮

</td></tr>

<tr>

<td colspan="2">Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0 = <a href="Arithmetical_set" title="Arithmetical set">arithmetical</a>

</td>

<td colspan="2">Σ0 <ω = Π0 <ω = Δ0 <ω = Σ1 0 = Π1 0 = Δ1 0 = boldface arithmetical

</td></tr>

<tr>

<td colspan="2">⋮

</td>

<td colspan="2">⋮

</td></tr>

<tr>

<td colspan="2">Δ0 α (α <a href="Recursive_ordinal" class="mw-redirect" title="Recursive ordinal">recursive</a>)

</td>

<td colspan="2">Δ0 α (α <a href="Countable_ordinal" class="mw-redirect" title="Countable ordinal">countable</a>)

</td></tr>

<tr>

<td>Σ0 α

</td>

<td>Π0 α

</td>

<td>Σ0 α

</td>

<td>Π0 α

</td></tr>

<tr>

<td colspan="2">⋮

</td>

<td colspan="2">⋮

</td></tr>

<tr>

<td colspan="2">Σ0 <a href="Church%E2%80%93Kleene_ordinal" class="mw-redirect" title="Church–Kleene ordinal">ωCK 1</a> = Π0 ωCK 1 = Δ0 ωCK 1 = Δ1 1 = <a href="Hyperarithmetical_theory" title="Hyperarithmetical theory">hyperarithmetical</a>

</td>

<td colspan="2">Σ0 <a href="First_uncountable_ordinal" title="First uncountable ordinal">ω1</a> = Π0 ω1 = Δ0 ω1 = Δ1 1 = B = <a href="Borel_set" title="Borel set">Borel</a>

</td></tr>

<tr>

<td>Σ1 1 = lightface analytic

</td>

<td>Π1 1 = lightface coanalytic

</td>

<td>Σ1 1 = A = <a href="Analytic_set" title="Analytic set">analytic</a>

</td>

<td>Π1 1 = CA = <a href="Coanalytic_set" title="Coanalytic set">coanalytic</a>

</td></tr>

<tr>

<td colspan="2">Δ1 2

</td>

<td colspan="2">Δ1 2

</td></tr>

<tr>

<td>Σ1 2

</td>

<td>Π1 2

</td>

<td>Σ1 2 = PCA

</td>

<td>Π1 2 = CPCA

</td></tr>

<tr>

<td colspan="2">Δ1 3

</td>

<td colspan="2">Δ1 3

</td></tr>

<tr>

<td>Σ1 3

</td>

<td>Π1 3

</td>

<td>Σ1 3 = PCPCA

</td>

<td>Π1 3 = CPCPCA

</td></tr>

<tr>

<td colspan="2">⋮

</td>

<td colspan="2">⋮

</td></tr>

<tr>

<td colspan="2">Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0 = <a href="Analytical_hierarchy" title="Analytical hierarchy">analytical</a>

</td>

<td colspan="2">Σ1 <ω = Π1 <ω = Δ1 <ω = Σ2 0 = Π2 0 = Δ2 0 = P = <a href="Projective_hierarchy" title="Projective hierarchy">projective</a>

</td></tr>

<tr>

<td colspan="2">⋮

</td>

<td colspan="2">⋮

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMoschovakis,_Yiannis_N.1980" class="citation book cs1">Moschovakis, Yiannis N. (1980). <a rel="nofollow" class="external text" href="https://archive.org/details/descriptivesetth0000mosc">Descriptive Set Theory</a>. North Holland. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-444-70199-0</bdi>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-04-02" href="https://en.wikipedia.org/wiki/?title=Pointclass&oldid=1216882110">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>